struct tSegment
{
	float2 p0;
	float2 p1;
};

struct gs_OutInstance {
	float4 position : TEXCOORD0;
	float4 scale_rotate : TEXCOORD1;
};

bool TestIntersection(float2 s0_p0, float2 s0_p1, float2 s1_p0, float2 s1_p1)
{
    float denominator = ((s0_p1.y - s0_p0.y) * (s1_p1.x - s1_p0.x)) - ((s0_p1.x - s0_p0.x) * (s1_p1.y - s1_p0.y));

    if (denominator == 0.0f)
    {
        return false;
    }
    else
    {
        float numerator_a = ((s0_p1.x - s0_p0.x) * (s1_p0.y - s0_p0.y)) - ((s0_p1.y - s0_p0.y) * (s1_p0.x - s0_p0.x));
        float numerator_b = ((s1_p1.x - s1_p0.x) * (s1_p0.y - s0_p0.y)) - ((s1_p1.y - s1_p0.y) * (s1_p0.x - s0_p0.x));

        float u_a = numerator_a / denominator;
        if (u_a < 0.0f || u_a > 1.0f)
            return false;

        float u_b = numerator_b / denominator;
        if (u_b < 0.0f || u_b > 1.0f)
            return false;

        return true;
    }
}

void CreateInstance(float3 position, float3 normal, float2 uv, float3 procedural_sample, inout PointStream<gs_OutInstance> instance_transforms)
{
/* 
uv - for sampling procedural
 */
	gs_OutInstance instance;
	instance.position = float4(position,0);
	instance.scale_rotate = float4(0,0,0,0);
	instance_transforms.Append(instance);
	
}

void InvertMatrix(float4x4 A, out float4x4 invA)
{
	float tmp[12];
	float src_pretranspose[16];
	float src[16];
	float dst[16];

	src_pretranspose[0] = A._11;	src_pretranspose[1] = A._12;	src_pretranspose[2] = A._13;	src_pretranspose[3] = A._14;
	src_pretranspose[4] = A._21;	src_pretranspose[5] = A._22;	src_pretranspose[6] = A._23;	src_pretranspose[7] = A._24;
	src_pretranspose[8] = A._31;	src_pretranspose[9] = A._32;	src_pretranspose[10] = A._33;	src_pretranspose[11] = A._34;
	src_pretranspose[12] = A._41;	src_pretranspose[13] = A._42;	src_pretranspose[14] = A._43;	src_pretranspose[15] = A._44;

	// Transpose float4x4
	for (int i = 0; i < 4; i++) {
	  src[i +  0] = src_pretranspose[i*4 + 0];
	  src[i +  4] = src_pretranspose[i*4 + 1];
	  src[i +  8] = src_pretranspose[i*4 + 2];
	  src[i + 12] = src_pretranspose[i*4 + 3];
	}

	// Calculate pairs for first 8 elements (cofactors) 
	tmp[0] = src[10] * src[15];
	tmp[1] = src[11] * src[14];
	tmp[2] = src[9]  * src[15];
	tmp[3] = src[11] * src[13];
	tmp[4] = src[9]  * src[14];
	tmp[5] = src[10] * src[13];
	tmp[6] = src[8]  * src[15];
	tmp[7] = src[11] * src[12];
	tmp[8] = src[8]  * src[14];
	tmp[9] = src[10] * src[12];
	tmp[10] = src[8] * src[13];
	tmp[11] = src[9] * src[12];

	// Calculate first 8 elements (cofactors)
	dst[0]  = tmp[0]*src[5] + tmp[3]*src[6] + tmp[4]*src[7];
	dst[0] -= tmp[1]*src[5] + tmp[2]*src[6] + tmp[5]*src[7];
	dst[1]  = tmp[1]*src[4] + tmp[6]*src[6] + tmp[9]*src[7];
	dst[1] -= tmp[0]*src[4] + tmp[7]*src[6] + tmp[8]*src[7];
	dst[2]  = tmp[2]*src[4] + tmp[7]*src[5] + tmp[10]*src[7];
	dst[2] -= tmp[3]*src[4] + tmp[6]*src[5] + tmp[11]*src[7];
	dst[3]  = tmp[5]*src[4] + tmp[8]*src[5] + tmp[11]*src[6];
	dst[3] -= tmp[4]*src[4] + tmp[9]*src[5] + tmp[10]*src[6];
	dst[4]  = tmp[1]*src[1] + tmp[2]*src[2] + tmp[5]*src[3];
	dst[4] -= tmp[0]*src[1] + tmp[3]*src[2] + tmp[4]*src[3];
	dst[5]  = tmp[0]*src[0] + tmp[7]*src[2] + tmp[8]*src[3];
	dst[5] -= tmp[1]*src[0] + tmp[6]*src[2] + tmp[9]*src[3];
	dst[6]  = tmp[3]*src[0] + tmp[6]*src[1] + tmp[11]*src[3];
	dst[6] -= tmp[2]*src[0] + tmp[7]*src[1] + tmp[10]*src[3];
	dst[7]  = tmp[4]*src[0] + tmp[9]*src[1] + tmp[10]*src[2];
	dst[7] -= tmp[5]*src[0] + tmp[8]*src[1] + tmp[11]*src[2];

	// Calculate pairs for second 8 elements (cofactors)
	tmp[0]  = src[2]*src[7];
	tmp[1]  = src[3]*src[6];
	tmp[2]  = src[1]*src[7];
	tmp[3]  = src[3]*src[5];
	tmp[4]  = src[1]*src[6];
	tmp[5]  = src[2]*src[5];
	tmp[6]  = src[0]*src[7];
	tmp[7]  = src[3]*src[4];
	tmp[8]  = src[0]*src[6];
	tmp[9]  = src[2]*src[4];
	tmp[10] = src[0]*src[5];
	tmp[11] = src[1]*src[4];

	// Calculate second 8 elements (cofactors)
	dst[8]   = tmp[0] * src[13]  + tmp[3] * src[14]  + tmp[4] * src[15];
	dst[8]  -= tmp[1] * src[13]  + tmp[2] * src[14]  + tmp[5] * src[15];
	dst[9]   = tmp[1] * src[12]  + tmp[6] * src[14]  + tmp[9] * src[15];
	dst[9]  -= tmp[0] * src[12]  + tmp[7] * src[14]  + tmp[8] * src[15];
	dst[10]  = tmp[2] * src[12]  + tmp[7] * src[13]  + tmp[10]* src[15];
	dst[10] -= tmp[3] * src[12]  + tmp[6] * src[13]  + tmp[11]* src[15];
	dst[11]  = tmp[5] * src[12]  + tmp[8] * src[13]  + tmp[11]* src[14];
	dst[11] -= tmp[4] * src[12]  + tmp[9] * src[13]  + tmp[10]* src[14];
	dst[12]  = tmp[2] * src[10]  + tmp[5] * src[11]  + tmp[1] * src[9];
	dst[12] -= tmp[4] * src[11]  + tmp[0] * src[9]   + tmp[3] * src[10];
	dst[13]  = tmp[8] * src[11]  + tmp[0] * src[8]   + tmp[7] * src[10];
	dst[13] -= tmp[6] * src[10]  + tmp[9] * src[11]  + tmp[1] * src[8];
	dst[14]  = tmp[6] * src[9]   + tmp[11]* src[11]  + tmp[3] * src[8];
	dst[14] -= tmp[10]* src[11 ] + tmp[2] * src[8]   + tmp[7] * src[9];
	dst[15]  = tmp[10]* src[10]  + tmp[4] * src[8]   + tmp[9] * src[9];
	dst[15] -= tmp[8] * src[9]   + tmp[11]* src[10]  + tmp[5] * src[8];

	// Calculate determinant
	float det = src[0]*dst[0] + src[1]*dst[1] + src[2]*dst[2] + src[3]*dst[3];

	// Calculate float4x4 inverse
	det = 1.0 / det;
	for (int j = 0; j < 16; j++)
	  dst[j] = dst[j] * det;
	

	invA._11 = dst[0];	invA._12 = dst[1];	invA._13 = dst[2];	invA._14 = dst[3];
	invA._21 = dst[4];	invA._22 = dst[5];	invA._23 = dst[6];	invA._24 = dst[7];
	invA._31 = dst[8];	invA._32 = dst[9];	invA._33 = dst[10];	invA._34 = dst[11];
	invA._41 = dst[12];	invA._42 = dst[13];	invA._43 = dst[14];	invA._44 = dst[15];
}

#define SAMPLE_DENSITY 15

[maxvertexcount(100)]
void gs_instancing(	triangleadj tGSDataum points[6],
			inout PointStream<gs_OutInstance> instance_transforms) {	

	tGSDataum vertex_a = points[0];
    tGSDataum vertex_b = points[2];
    tGSDataum vertex_c = points[4];

    float2 uv_a = vertex_a.uv12;
    float2 uv_b = vertex_b.uv12;
    float2 uv_c = vertex_c.uv12;

    float3 pos_a = vertex_a.position_ws;
    float3 pos_b = vertex_b.position_ws;
    float3 pos_c = vertex_c.position_ws;
    
    //Define triange edges as the tangents of the triangle geometry
    float3 ve_10 = pos_a - pos_b;
    float3 ve_12 = pos_c - pos_b;
    float3 n = cross(ve_10, ve_12);

    //Define uv edges as the tangents of the triangle's uv coordinates
    float3 uv1_edge = 0.0f; uv1_edge.xy = uv_a - uv_b;
    float3 uv2_edge = 0.0f; uv2_edge.xy = uv_c - uv_b;

    //Construct float4x4 A to transform from tangent space to object space
    float4x4 A = float4x4(
        ve_10.x, ve_10.y, ve_10.z, 0,
        ve_12.x, ve_12.y, ve_12.z, 0,
        n.x, n.y, n.z, 0,
        pos_b.x, pos_b.y, pos_b.z, 1);

    //Construct float4x4 B whose inverse transforms from uv space to tangent space
    float4x4 B = float4x4(
        uv1_edge.x, uv1_edge.y, 0, 0,
        uv2_edge.x, uv2_edge.y, 0, 0,
        0, 0, 1, 0,
        uv_b.x, uv_b.y, 0, 1);

    float4x4 InverseB;
	InvertMatrix(B, InverseB);

	float4x4 test = mul(B, InverseB);
     
    //Define a range rectangle around the triangle in UV space
    float2 start = uv_a + test._11 + test._21 + test._31 + test._41;
    float2 end = uv_a;

    if (uv_b.x < start.x) start.x = uv_b.x;
    else if (uv_b.x > end.x) end.x = uv_b.x;

    if (uv_c.x < start.x) start.x = uv_c.x;
    else if (uv_c.x > end.x) end.x = uv_c.x;

    if (uv_b.y < start.y) start.y = uv_b.y;
    else if (uv_b.y > end.y) end.y = uv_b.y;

    if (uv_c.y < start.y) start.y = uv_c.y;
    else if (uv_c.y > end.y) end.y = uv_c.y;
    
    //Step size in each dimension
    float x_increment = ((end.x - start.x) / (float)SAMPLE_DENSITY);
    float y_increment = ((end.y - start.y) / (float)SAMPLE_DENSITY);
	
	int saftey = 0;
	if(x_increment != 0.0f && y_increment != 0.0f) {

		//Step across the rectangle in UV space
		for (float i = start.x; i < end.x; i += x_increment)
		{
			for (float j = start.y; j < end.y; j += y_increment)
			{
				saftey++;
				if(saftey > 100)
					return;
				float2 t_a = float2(i, j);
				float2 t_b = t_a + float2(0.0f, 1.5f * (end.y - start.y));

				//Determine if the sample is contained within the triangle. An odd summation
				//means this UV sample position is contained within the triangles UV coordinates
				bool isContained =  ((TestIntersection(t_a, t_b, uv_a, uv_b) ? 1 : 0) +
									(TestIntersection(t_a, t_b, uv_b, uv_c) ? 1 : 0) +
									(TestIntersection(t_a, t_b, uv_c, uv_a) ? 1 : 0)) % 2 != 0;

				if (isContained)
				{   				
					//Transform the UV sample from UV space, to tangenet space, to object space
					float4 uv = float4(i, j, 0, 1);

					float3 procedural_sample = 1;// Procedural_Noise((float3)uv, noiseParam_decal);
					//if(dot( procedural_sample,procedural_sample ) > 0.25f ) 
					{

						float4 triangle_coord = mul(uv, InverseB);
						float3 object_pos = (float3)mul(triangle_coord, A);

						CreateInstance(object_pos, n, float2(0,0) ,procedural_sample, instance_transforms);
					}
					
					//object_pos is the position of the UV cooridnate in object space
					//m_GeometryViewport.AddCross(object_pos.x, object_pos.z, c);
					//m_UVViewport.AddCross(uv.x, uv.y, c);
				}
			}
		}
	}
	instance_transforms.RestartStrip();
}